//
// Created by f12160c on 2018/7/25.
//

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>

#include "leetcode/leetcode.hpp"

using namespace std;

vector<string> Solution::letterCombinations(string digits) {
    const static char letters[][4] = {
            {'a', 'b', 'c'},
            {'d', 'e', 'f'},
            {'g', 'h', 'i'},
            {'j', 'k', 'l'},
            {'m', 'n', 'o'},
            {'p', 'q', 'r', 's'},
            {'t', 'u', 'v'},
            {'w', 'x', 'y', 'z'}
    };
    const static int letter_number[] = {3, 3, 3, 3, 3, 4, 3, 4};
    vector<string> ret;
    auto n = digits.size();
    if (n == 0){
        return ret;
    }
    int digits_size[n];

    char *p;
    int total_size, tmp;

    digits_size[n - 1] = 1;
    for (int i = n - 1; i > 0; i--) {
        tmp = digits[i] - '2';
        if((tmp < 0) || (tmp > sizeof(letter_number)))
        {
            return ret;
        }
        digits_size[i - 1] = letter_number[tmp] * digits_size[i];
    }
    tmp = digits[0] - '2';
    if((tmp < 0) || (tmp > sizeof(letter_number)))
    {
        return ret;
    }
    total_size = letter_number[tmp] * digits_size[0];

    p = new char[total_size*n];
    for(int i = 0; i < n; i++) {
        int m = 0;
        for(int j = 0; j < total_size; j += digits_size[i]) {
            char letter = letters[digits[i] - '2'][m];
            m++;
            if( m == letter_number[digits[i] - '2']) {
                m = 0;
            }
            for (int k = 0; k < digits_size[i]; k++)
            {
                p[(j + k)*n + i] = letter;
            }
        }
    }

    for(int i = 0; i < total_size; i++)
    {
        ret.push_back(string(&p[i*n], n));
    }
    delete p;
    return ret;
}

vector<string> string_group_add(vector<string> &current, string &digits, int level)
{
    vector<string> ret;
    const static char letters[][4] = {
            {'a', 'b', 'c'},
            {'d', 'e', 'f'},
            {'g', 'h', 'i'},
            {'j', 'k', 'l'},
            {'m', 'n', 'o'},
            {'p', 'q', 'r', 's'},
            {'t', 'u', 'v'},
            {'w', 'x', 'y', 'z'}
    };
    const static int letter_number[] = {3, 3, 3, 3, 3, 4, 3, 4};
    if(level == digits.size())
    {
        return current;
    }
    for(int i = 0; i < current.size(); i++)
    {
        int tmp = digits[level] - '2';
        for( int j = 0; j < letter_number[tmp]; j++) {
            ret.push_back(current[i] + letters[tmp][j]);
        }
    }
    return string_group_add(ret, digits, level + 1);

}
vector<string> Solution::letterCombinations_1(string digits) {
    vector<string> ret;
    if(digits.size() == 0)
    {
        return ret;
    }
    ret.push_back("");
    return string_group_add(ret, digits, 0);
}